package lib

//link to 55
func init() {
	Probs = append(Probs, Problem{
		Num:         45,
		Discription: "到达数组末尾的最小跳数",
		Level:       2,
		Labels: map[string]int{
			"贪心":   1,
			"双指针滑动": 1,
		},
	})
}

// Jump 计算每一朓的范围；根据前一跳所能到达的范围计算后一跳所能到达的范围
//  @param nums
//  @return int
func Jump(nums []int) int {
	if len(nums) <= 1 {
		return 0
	}

	count := 0
	preStart := 0
	preEnd := 0
	for {
		//计算当前跳能达到最远距离
		tempEnd := preEnd
		for i := preStart; i <= preEnd; i++ {
			tempEnd = max(tempEnd, nums[i]+i)
		}

		count++
		if tempEnd >= len(nums)-1 {
			return count
		}

		//最小距离是前一轮的最大距离+1，因为这个值肯定会被覆盖到
		preStart = preEnd + 1
		preEnd = tempEnd
	}
}
